import random

def bubble(lst):
    n = len(lst)
    for l in range(n-1,0,-1):
        for i in range(l):
            if lst[i] > lst[i+1] :
                lst[i],lst[1+i]=lst[i+1],lst[i]
    return lst

def bubble_better(lst):
    n = len(lst)
    for l in range(n-1,0,-1):
        go = False
        for i in range(l):
            if lst[i]> lst[i+1] :
                go = True
                lst[i],lst[1+i]=lst[i+1],lst[i]
        if not go: #没有交换就已经排好
            break
    return lst

def select(lst):
    n = len(lst)
    for l in range(n,0,-1):
        max = 0
        for i in range(l):
            if lst[max]< lst[i] :
                max = i #记录最大值的索引
        else:
            lst[max],lst[i]=lst[i],lst[max]
    return lst

if __name__ == "__main__":
    n = 1000
    lst = list({random.randrange(n,10*n-1) for _ in range(n)})
    print(bubble(lst)==sorted(lst))
    print(select(lst)==sorted(lst))